[/
  Copyright 2020 Ilia Shirobokov.
  Copyright 2020 Alisa Cherniaeva.

  Distributed under the Boost Software License, Version 1.0.
  (See accompanying file LICENSE_1_0.txt or copy at
  http://www.boost.org/LICENSE_1_0.txt).
]

[section:modular_adaptor modular_adaptor]

[pre
[*Table of Contents]
 [link boost_multiprecision.tut.modular.modular_adaptor.api modular_adaptor API]
     [link boost_multiprecision.tut.modular.modular_adaptor.const_oper Constructors and Operators]
     [link boost_multiprecision.tut.modular.modular_adaptor.getter Getters]
     [link boost_multiprecision.tut.modular.modular_adaptor.members Class member functions]
        [link compare `compare(const modular_adaptor& o)`]
        [link compare_t `compare(const T& val)`]
        [link negate `negate()`]
        [link str `str(std::streamsize dig, std::ios_base::fmtflags f)`]
        [link swap `swap(modular_adaptor& o)`]
     [link boost_multiprecision.tut.modular.modular_adaptor.other Class Related Functions]
        [link eval_redc `eval_redc(Backend& result, const modular_params<Backend>& mod)`]
        [link find_modular_pow `find_modular_pow(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& b, Backend& exp)`]
        [link window_bits `window_bits(size_t exp_bits))`]
     [link boost_multiprecision.tut.modular.modular_adaptor.backend_requirements Backend Required Functions]
        [link assign_components `assign_components(modular_adaptor<Backend>& result, const T& a, const V& b)`]
        [link eval_abs `eval_abs(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& val)`]
        [link eval_add `eval_add(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& o)`]
        [link eval_bitwise_and `eval_bitwise_and(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& v)`]
        [link eval_bitwise_or `eval_bitwise_or(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& v)`]
        [link eval_bitwise_xor `eval_bitwise_xor(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& v)`]
        [link eval_convert_to `eval_convert_to(Result* result, const modular_adaptor<Backend>& val)`]
        [link eval_divide `eval_divide(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& o)`]
        [link eval_eq `eval_eq(const modular_adaptor<Backend>& a, const T& b)`]
        [link eval_get_sign `eval_get_sign(const modular_adaptor<Backend>&)`]
        [link eval_is_zero `eval_is_zero(const modular_adaptor<Backend>& val)`]
        [link eval_left_shift `eval_left_shift(modular_adaptor<Backend>& t, UI i)`]
        [link eval_left_shift_with_v `eval_left_shift(modular_adaptor<Backend>& t, const modular_adaptor<Backend>& v, UI i)`]
        [link eval_modulus `eval_modulus(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& o)`]
        [link eval_multiply `eval_multiply(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& o)`]
        [link eval_pow `eval_pow(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& b, const modular_adaptor<Backend>& e)`]
        [link eval_pow_backend_e `eval_pow(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& b, const Backend& e)`]
        [link eval_right_shift `eval_right_shift(modular_adaptor<Backend>& t, UI i)`]
        [link eval_right_shift_with_v `eval_right_shift(modular_adaptor<Backend>& t, const modular_adaptor<Backend>& v, UI i)`]
        [link eval_sqrt `eval_sqrt(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& val)`]
        [link eval_subtract `eval_subtract(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& o)`]
]

``
    namespace boost {
    namespace multiprecision {
    namespace backends {

        template <typename Backend>
        class modular_adaptor;
    }}
``
The class template `modular_adaptor` converts any existing integer backend into a number backend for [@https://en.wikipedia.org/wiki/Modular_arithmetic modular arithmetic].

The class `modular_adaptor` contains two parts.

* The first part is a /number/ which is defined by the given integer backend. In math, it is known as /residue class/ or /congruence class/. 
* The second part is /modulus/ which is an instance of [link boost_multiprecision.tut.modular.modular_adaptor.modular_params `modular_params`].

[h2:api modular_adaptor API]

[h4:const_oper Constructors and Operators]

[table `modular_adaptor` constructors
    [ [ Signature ] [ Comments ] ]
    [ [ `modular_adaptor()` ] [ ] ]
    [ [ `modular_adaptor(const modular_adaptor& o)` ] [ ] ]
    [ [ `modular_adaptor(modular_adaptor&& o)` ] [ ] ]
    [ [ `modular_adaptor(const Backend& val, const modular_params<Backend>& mod)` ] [ ] ]
    [ [ `modular_adaptor(const Backend& val, const Backend& mod)` ] [ ] ]
    [ [ `modular_adaptor(Backend& val, Backend& mod)` ] [ ] ]
    [ [ `modular_adaptor(const Backend& val)` ] [ Creates `modular_adaptor` instance with modulus equals to zero ] ]
    [ [ `modular_adaptor(const modular_params<Backend>& mod)` ] [ Creates `modular_adaptor` instance with value (residue class) equals to zero ] ]
]

[table `modular_adaptor` operators
    [ [ Signature ] [ Comments ] ]
    [ [ `modular_adaptor& operator=(const modular_adaptor& o)` ] [ ] ]
    [ [ `modular_adaptor& operator=(modular_adaptor&& o)` ] [ ] ]
    [ [ `modular_adaptor& operator=(const char* s)` ] [ ] ]
]

[h4:getter Getters]

[#base_data]
[role blue `base_data`]

`inline Backend& base_data()`

`inline Backend const& base_data() const`

Returns the value of the `modular_adaptor` (residue class of the number by modulo).

[#mod_data]
[role blue `mod_data`]

`inline modular_params<Backend>& mod_data()`

`inline const modular_params<Backend>& mod_data() const`

Returns [link boost_multiprecision.tut.modular.modular_adaptor.modular_params `modular_params`] that contains modulus and additional data.


[h4:members Class Member Functions]

[#compare] 
[role blue `int compare(const modular_adaptor& o) const`]

Compares bases (see [link base_data `base_data()`]) of two `modular_adaptor`.

Modulus values of both `modular_adaptor` have to be equal. 

In other case, the function throws the `std::runtime_error` exception.

[#compare_t] 
[role blue `template <class T> int compare(const T& val) const`]

Compares base (see [link base_data `base_data()`]) of `modular_adaptor` to `val`.

Modulus values of the  `modular_adaptor` have to be less than `val`. 

In other case, the function throws the `std::runtime_error` exception.

[#negate] 
[role blue `inline void negate()`]

Multiply the number by -1. 

According to the modular arithmetic rules, the result equals /modulus - number/ (always > 0).

[#str] 
[role blue `inline std::string str(std::streamsize dig, std::ios_base::fmtflags f) const`]

Returns the string representation of base (see [link base_data `base_data()`]) with `dig` digits
and formatted according to the flags set in `f`. 

If `dig` is zero, then returns as many digits as are required to reconstruct the original value. 

[#swap] 
[role blue `inline void swap(modular_adaptor& o)`]

Swap both base value and modulus values between two instances of `modular_adaptor`.


[h4:other Class Related Functions]
[#eval_redc] 
[role blue `template <class Backend> inline void eval_redc(Backend& result, const modular_params<Backend>& mod)`]

Computes `result` by modulo set in `modular_params`.

Currently, `modular_params` doesn't allow choosing a reduction algorithm. 

By default, `modular_params` uses [@https://en.wikipedia.org/wiki/Barrett_reduction Barrett reduction] for even numbers and [@https://en.wikipedia.org/wiki/Montgomery_modular_multiplication Montgomery reduction] otherwise. 


[#find_modular_pow] [role blue `template <class Backend> inline void find_modular_pow(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& b, Backend& exp)`]

Calculates modular exponentiation, i.e. `b.base_data() ^ exp mod m` where `m` is a modulus of `b` (see [link boost_multiprecision.tut.modular.modular_adaptor.getter `mod_data()`]).

The implementation is based on fixed window algorithm with Montgomery representation (e.g. see page 4 of the [@https://eprint.iacr.org/2011/239.pdf paper]).

[#window_bits] [role blue `size_t window_bits(size_t exp_bits))`]

Returns the window size for exponentiation operation (see [link eval_pow `eval_pow`] or [link find_modular_pow `find_modular_pow`]).
Notice that you do not need to invoke `window_bits` manually. 

[h4:backend_requirements Backend Required Functions]

[#assign_components] [role blue `template <class Backend, class T, class V> inline void assign_components(modular_adaptor<Backend>& result, const T& a, const V& b)`]

Assign to `result` base value the value `a` and `result` mod value the value `b` (see [link boost_multiprecision.tut.modular.modular_adaptor.getter Getters section] ).

The base value is represented in the form required for the reduction algorithm used (see [link eval_redc `eval_redc`]).

[#eval_abs] [role blue `template <class Backend> inline void eval_abs(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& val)`]

Set `result` base data to the absolute value of the `val` base data (see [link base_data `base_data()`]). 

[#eval_add] 
[role blue `template <class Backend> inline void eval_add(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& o)`]

Adds `o` base value to `result` base value (see [link base_data `base_data()`]). 

Modulus values of both `modular_adaptor` have to be equal. 

The result is reduced by modulo.

[#eval_bitwise_and] [role blue `template <class Backend> inline void eval_bitwise_and(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& v)`]

Converts both `result` and `b` to a regular numbers, evaluates "bitwise and" operation over them following `Backend` rules, and converts the result back to `modular_adaptor`.  

Stores the result in `result` with its original modulus value.

[#eval_bitwise_or] [role blue `template <class Backend> inline void eval_bitwise_or(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& v)`]

Converts both `result` and `b` to a regular numbers, evaluates "bitwise or" operation over them following `Backend` rules, and converts the result back to `modular_adaptor`.  

Stores the result in `result` with its original modulus value.

[#eval_bitwise_xor] [role blue `template <class Backend> inline void eval_bitwise_xor(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& v)`]

Converts both `result` and `b` to a regular numbers, evaluates "bitwise xor" operation over them following `Backend` rules, and converts the result back to `modular_adaptor`.  

Stores the result in `result` with its original modulus value.

[#eval_convert_to] 
[role blue `template <class Result, class Backend> inline typename boost::disable_if_c<boost::is_complex<Result>::value>::type eval_convert_to(Result* result, const modular_adaptor<Backend>& val)`]

Converts a residue class handed by `modular_adaptor` (see [link base_data `base_data()`]) to the type of `result`.

Notice that modulus data (see [link mod_data `mod_data()`]) doesn't affect this conversion. 

[#eval_divide] [role blue `template <class Backend> inline void eval_divide(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& o)`]

Divides `result` base value by `o` base value (see [link base_data `base_data()`]). 

Modulus values of the both `modular_adaptor` have to be equal. 
The result is reduced by modulo.

[#eval_eq] [role blue `template <class Backend, class T> inline typename boost::enable_if<boost::is_arithmetic<T>, bool> ::type eval_eq(const modular_adaptor<Backend>& a, const T& b)`]

Returns `true` if `a` and `b` are equal in value.

Notice that `a` and `b` must have the same modulus value. 

In other case, the function throws the `std::runtime_error` exception.

[#eval_get_sign] [role blue `template <class Backend> inline int eval_get_sign(const modular_adaptor<Backend>&)`]

Returns a value < zero if the base value (see [link base_data `base_data()`]) is negative,
a value > zero if the base value is positive, and zero if the base value is zero. 

[#eval_is_zero] [role blue `template <class Backend> inline bool eval_is_zero(const modular_adaptor<Backend>& val)`]

Returns true if the base value (see [link base_data `base_data()`]) of `val` is zero, otherwise false.

[#eval_left_shift] [role blue `template <class Backend, class UI> inline void eval_left_shift(modular_adaptor<Backend>& t, UI i)`]

Converts `t` to a regular number, evaluates left shift over it following `Backend` rules, and converts the result back to `modular_adaptor` with the same modulus. 

Stores the result in `t`.

[#eval_left_shift_with_v] [role blue `template <class Backend, class UI> inline void eval_left_shift(modular_adaptor<Backend>& t, const modular_adaptor<Backend>& v, UI i)`]

Converts `v` to a regular number, evaluates right shift over it following `Backend` rules, and converts the result back to `modular_adaptor` with the same modulus.  

Stores the result in `t`.

[#eval_modulus] [role blue `template <class Backend> inline void eval_modulus(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& o)`]

Compute `result` base value by  modulo `o` base value (see [link base_data `base_data()`]).

Uses `Backend` reduction algorithm. 

Modulus values of the both `modular_adaptor` have to be equal. 
The result is reduced by the modulus value.

Notice that the same functionality is provided by [link eval_redc `eval_redc`] which is prefered method while working with `modular_adaptor`.

[#eval_multiply] [role blue `template <class Backend> inline void eval_multiply(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& o)`]

Multiply `o` base value to `result` base value (see [link base_data `base_data()`]). 

Modulus values of the both `modular_adaptor` have to be equal. 

The result is reduced by the modulus value.

[#eval_pow] [role blue `template <class Backend> inline void eval_pow(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& b, const modular_adaptor<Backend>& e)`]

Calculates modular exponentiation, i.e. `b.base_data() ^ e.base_data() mod m` where `m` is a modulus of `b` (see [link mod_data `mod_data()`]).

The implementation is based on fixed window algorithm with Montgomery representation (e.g. see page 4 of the [@https://eprint.iacr.org/2011/239.pdf paper]).

[#eval_pow_backend_e] [role blue `template <class Backend> inline void eval_pow(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& b, const Backend& e)`]

Calculates modular exponentiation, i.e. `b.base_data() ^ e mod m` where `m` is a modulus of `b` (see [link mod_data `mod_data()`]).

The implementation is based on fixed window algorithm with Montgomery representation (e.g. see page 4 of the [@https://eprint.iacr.org/2011/239.pdf paper]).

[#eval_right_shift] [role blue `template <class Backend, class UI> inline void eval_right_shift(modular_adaptor<Backend>& t, UI i)`]

Converts `t` to a regular number, evaluates right shift over it following `Backend` rules, and converts the result back to `modular_adaptor` with the same modulus.  

Stores the result in `t`.

[#eval_right_shift_with_v] [role blue `template <class Backend, class UI> inline void eval_right_shift(modular_adaptor<Backend>& t, const modular_adaptor<Backend>& v, UI i)`]

Converts `v` to a regular number, evaluates right shift over it following `Backend` rules, and converts the result back to `modular_adaptor` with the same modulus.  

Stores the result in `t`.

[#eval_sqrt] [role blue `template <class Backend> inline void eval_sqrt(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& val)`]

Assign to `result` base value the square root of `o` base value (see [link base_data `base_data()`]). 

This value is not reduced on modulo.

[#eval_subtract] 
[role blue `template <class Backend> inline void eval_subtract(modular_adaptor<Backend>& result, const modular_adaptor<Backend>& o)`]

Subtract `o` base value from `result` base value (see [link base_data `base_data()`]). 

Modulus values of both `modular_adaptor` have to be equal. 
The result is reduced by the modulus value.


[include tutorial_modular_params.qbk]
[endsect] [/section:modular_adaptor modular_adaptor]
